Background: Olfactomedin 4 (OLFM4), a secreted glycoprotein of the olfactomedin family, plays important roles in innate immunity, inflammation, and cancer. We previously found that the OLFM4 gene is deleted in 1025% of human prostate-cancer tissues, and that expression was lost in more than 50% of advanced prostate cancers. The purpose of this study was to evaluate the relationship of OLFM4 expression with human prostate-cancer progression and methylation of the OLFM4 gene promoter region. Methods: OLFM4 protein expression in prostate-cancer tissues was detected using immunohistochemical staining with OLFM4 polyclonal antibody. The CpG site methylation status of the OLFM4 gene promoter region was examined with pyrosequencing. OLFM4 mRNA expression, methylation, and clinical data were downloaded from the GSE21032 dataset for 28 normal and 174 prostate-cancer patients (153 with primary tumors and 21 with metastatic tumors) and from The Cancer Genome Atlas (TCGA) for 333 primary prostate adenocarcinomas. Results: OLFM4 protein and mRNA expression was significantly reduced in human prostate-cancer tumors compared with normal adjacent tissue, and OLFM4 mRNA expression in metastatic tumors was significantly lower than that observed in primary prostate-cancer tumors. Further, reduced OLFM4 expression was associated with OLFM4 gene promoter region CpG site hypermethylation in primary prostate cancer. Overall methylation of the OLFM4 gene promoter region was significantly higher in prostate-cancer tissues compared with normal prostate tissues. Exposure to the methylation inhibitor 5-aza-2-deoxycytidine (5 M) significantly increased OLFM4 expression in both normal prostate cell lines as well as metastatic prostate-cancer cell lines. Reduced OLFM4 expression was associated with increased pre-operative serum prostate specific antigen levels, higher Gleason scores, and an increased likelihood of biochemical recurrence of human prostate cancer. Conclusions: Reduced OLFM4 expression is associated with human prostate-cancer progression, and with increased CpG site methylation in the OLFM4 gene promoter region in primary prostate cancer. These results imply that OLFM4 expression may be regulated by DNA methylation during the progression of prostate cancer. Based on these findings, OLFM4 may represent a novel candidate biomarker for predicting aggressive progression of human prostate cancer.